package leetcode.easy;

/**
 * 实现strStr()函数。
 * 给定一个haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 * 示例 1:
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 * 示例 2:
 * 输入: haystack = "aaaaa", needle = "bba"
 * 输出: -1
 *
 * @author TANGYE
 * @date 2021/1/25 9:30 下午
 **/
public class Str {

    public static void main(String[] args) {
        System.out.println(strStr("hello","ll"));
        //abccba bccbafff  abccbafff
        //"mississippi"
        //"a"
    }

    public static int strStr(String haystack, String needle) {
        if (null == needle || "".equals(needle)){
            return 0;
        }
        if (null == haystack || "".equals(haystack)){
            return -1;
        }
        char[] haystackArr = haystack.toCharArray();
        char[] needleArr = needle.toCharArray();
        if (haystackArr.length < needleArr.length){
            return -1;
        }

        int max = haystackArr.length - needleArr.length;
        for (int i = 0; i <= max; i++){
            int j = 0;
            if (haystackArr[i] != needleArr[j]){
                while (++i <= max && haystackArr[i] != needleArr[j]);
            }
            if (i <= max){
                int n = i;
                int end = 0;
                while (j < needleArr.length && haystackArr[n++] == needleArr[j++]){
                    end++;
                }
                if (end == needleArr.length){
                    return i;
                }
            }
        }
        return -1;
    }
}
